`
https://leetcode.cn/problems/lru-cache/
`

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.map = new Map()
    this.cache = new DoubleLinkList()
  }

  get(key) {
    if (!this.map.has(key)) {
      return -1;
    }
    // 将该数据提升为最近使用的
    this._makeRecently(key);
    return this.map.get(key).val;
  }

  put(key, value) {
    if (this.map.has(key)) {
      // 删除旧的数据
      this._deleteKey(key);
      // 新插入的数据为最近使用的数据
      this._addRecently(key, value);
      return;
    }

    if (this.capacity === this.cache.size) {
      // 删除最久未使用的元素
      this._removeLeastRecently();
    }
    // 添加为最近使用的元素
    this._addRecently(key, value);
  }

  // 将某个 key 提升为最近使用的
  _makeRecently(key) {
    const x = this.map.get(key)
    // 先从链表中删除这个节点
    this.cache.remove(x)
    // 重新插到队尾
    this.cache.addLast(x)
  }

  // 添加最近使用的元素
  _addRecently(key, value) {
    const x = new Node(key, value)
    // 链表尾部就是最近使用的元素
    this.cache.addLast(x)
    // 别忘了在 map 中添加 key 的映射
    this.map.set(key, x)
  }

  // 删除某一个 key
  _deleteKey(key) {
    const x = this.map.get(key)
    // 从链表中删除
    this.cache.remove(x)
    // 从 map 中删除
    this.map.delete(key)
  }

  // 删除最久未使用的元素
  _removeLeastRecently() {
    // 链表头部的第一个元素就是最久未使用的
    const deletedNode = this.cache.removeFirst()
    // 同时别忘了从 map 中删除它的 key
    const deletedKey = deletedNode.key
    this.map.delete(deletedKey)
  }
}

/** 
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/

// 链表结点
class Node {
  constructor(k, v) {
    this.key = k
    this.val = v
    this.next = null
    this.prev = null
  }
}

// 双向链表
class DoubleLinkList {
  constructor() {
    // 虚拟头尾结点
    this.head = new Node(0, 0)
    this.tail = new Node(0, 0)

    this.size = 0

    // init
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  // 在链表尾部添加节点 x，时间 O(1)
  addLast(node) {
    node.prev = this.tail.prev
    node.next = this.tail
    this.tail.prev.next = node
    this.tail.prev = node
    this.size++
  }
  // 删除链表中的 x 节点（x 一定存在）
  // 由于是双链表且给的是目标 Node 节点，时间 O(1)
  remove(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
    this.size--
  }

  // 删除链表中第一个节点，并返回该节点，时间 O(1)
  removeFirst() {
    if (this.head.next == this.tail)
      return null;
    const first = this.head.next;
    this.remove(first);
    return first;
  }
}

// test
const cache = new LRUCache(2)